package leetcode;

class Solution3 {
    /**
     * 63. 不同路径 II
     * https://leetcode.cn/problems/unique-paths-ii/description/
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //列数
        int row = obstacleGrid[0].length;
        //行数
        int col = obstacleGrid.length;

        int[][] dp = new int[col + 1][row + 1];
        
        dp[0][1] = 1;
        //遍历dp表，注意，每次遍历都要判断当前位置是不是障碍物，如果是当前位置就设置为0，不是就左边+上边
        for(int i = 1; i < col + 1; i++) {
            for(int j = 1; j < row + 1; j++) {
                if(obstacleGrid[i - 1][j - 1] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[col][row];
    }
}